#include<iostream>
#include<vector>
using namespace std;

//构建next数组
void getnext(vector<int>& next,const string &substr)
{
	next[0] = -1;
	next[1] = 0;
	int i = 2;
	int k = 0;

	for (; i < substr.size(); i++)
	{
		//p[i-1]==p[k]
		if (k == -1 || substr[i - 1] == substr[k])
		{
			next[i] = k + 1;
			k++;
			i++;
		}
		else
		{
			k = next[k];
		}
	}
}

//找到子串并且返回子串的其实下标
int  KMP(const string& str, const string& substr, int&& pos)
{
	//先检查两个串是否合法
	if (str.size() == 0 || substr.size() == 0)return -1;
	int strlen = str.size();
	int sublen = substr.size();
	//检查pos是否合法
	if (pos < 0 || pos >= sublen)return -1;

	int i = pos;//遍历主串
	int j = 0;//遍历子串

	//构建next数组
	vector<int>next(sublen);

	getnext(next,substr);


	while (i < strlen && j < sublen)
	{
		//如果匹配成功---两个指针向后移动
		if (j==-1||str[i] == substr[j])
		{
			++i;
			++j;
		}
		else//如果不匹配j指针就回退到next[j];
		{
			j = next[j];
		}
	}

	//如果匹配整个子串成功
	if (j == sublen)
	{
		return i - j;//返回主串中子串的起始下标
	}
	else
		return -1;//否则就是没有找到
}


int main()
{
	string str("ascalbvjbdvkbkabva");
	string substr("bvjb");
	cout << KMP(str, substr, 0);
	return 0;
}
